package edu.princeton.cs.algs4;

import edu.princeton.cs.stdlib.StdOut;

/*************************************************************************
 * Compilation: javac Cycle.java Dependencies: Graph.java Stack.java
 * 
 * Identifies a cycle. Runs in O(E + V) time.
 * 
 *************************************************************************/

public class Cycle {
	private boolean[] marked;
	private int[] edgeTo;
	private Stack<Integer> cycle;

	public Cycle(Graph G) {
		if (hasSelfLoop(G))
			return;
		if (hasParallelEdges(G))
			return;
		marked = new boolean[G.V()];
		edgeTo = new int[G.V()];
		for (int v = 0; v < G.V(); v++)
			if (!marked[v])
				dfs(G, -1, v);
	}

	// does this graph have a self loop?
	// side effect: initialize cycle to be self loop
	private boolean hasSelfLoop(Graph G) {
		for (int v = 0; v < G.V(); v++) {
			for (int w : G.adj(v)) {
				if (v == w) {
					cycle = new Stack<Integer>();
					cycle.push(v);
					cycle.push(v);
					return true;
				}
			}
		}
		return false;
	}

	// does this graph have two parallel edges?
	// side effect: initialize cycle to be two parallel edges
	private boolean hasParallelEdges(Graph G) {
		marked = new boolean[G.V()];

		for (int v = 0; v < G.V(); v++) {

			// check for parallel edges incident to v
			for (int w : G.adj(v)) {
				if (marked[w]) {
					cycle = new Stack<Integer>();
					cycle.push(v);
					cycle.push(w);
					cycle.push(v);
					return true;
				}
				marked[w] = true;
			}

			// reset so marked[v] = false for all v
			for (int w : G.adj(v)) {
				marked[w] = false;
			}
		}
		return false;
	}

	public boolean hasCycle() {
		return cycle != null;
	}

	public Iterable<Integer> cycle() {
		return cycle;
	}

	private void dfs(Graph G, int u, int v) {
		marked[v] = true;
		for (int w : G.adj(v)) {

			// short circuit if cycle already found
			if (cycle != null)
				return;

			if (!marked[w]) {
				edgeTo[w] = v;
				dfs(G, v, w);
			}

			// check for cycle (but disregard reverse of edge leading to v)
			else if (w != u) {
				cycle = new Stack<Integer>();
				for (int x = v; x != w; x = edgeTo[x]) {
					cycle.push(x);
				}
				cycle.push(w);
				cycle.push(v);
			}
		}
	}

	// test client
	public static void main(String[] args) {
		int V = Integer.parseInt(args[0]);
		int E = Integer.parseInt(args[1]);
		Graph G = new Graph(V, E);
		System.out.println(G);

		Cycle finder = new Cycle(G);
		if (finder.hasCycle()) {
			for (int v : finder.cycle()) {
				StdOut.print(v + " ");
			}
			StdOut.println();
		} else {
			StdOut.println("Graph is acyclic");
		}
	}

}
